package com.backpack;

/**
 * 不同的子序列
 * 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
 * 输入：s = "rabbbit", t = "rabbit"
 * 输出：3
 */
public class DistinctSubsequences0119_115 {
    public int numDistinct(String s, String t) {
        //动态规划
        //dp 含义：表示 以[i-1]下标元素结尾的 s 子字符串中 含有 以[j-1]下标元素结尾的 t 子字符串 的个数
        int[][] dp = new int[s.length()+1][t.length()+1];
        //返回值 dp[s.length()][t.length()];
        //初始化：根据递推公式和dp 含义，需要初始化dp[i][0]=1,dp[0][j]=0,dp[0][0]=1
        for (int i = 0; i < s.length(); i++) {
            dp[i][0] =1;
        }


        //递推公式：
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if(s.charAt(i-1) == t.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; //比如：s=bagg,t=bag 当 i=3,j=2时：模拟两种情况：1、使用s中当前下标，2、不使用s的当前下标元素（使用前一个下标元素）
                }else {
                    dp[i][j] = dp[i-1][j]; //不相等时，就不考虑当前s 的下标元素
                }
            }
        }

        return dp[s.length()][t.length()];
    }
}
